class Solution {
public:
    int dx[4] = {0, 1, 0, -1};
    int dy[4] = {1, 0, -1, 0};
    // state：0表示右，1表示下，2表示左，3表示上
    void dfs(int x, int y, int mx, int my, int state,
             vector<vector<int>>& matrix, vector<vector<bool>>& vis,
             vector<int>& ans) {
        if (!(x >= 0 && x < mx && y >= 0 && y < my) || vis[x][y])
            return;
        vis[x][y] = true;
        ans.push_back(matrix[x][y]);
        int x1 = x + dx[state];
        int y1 = y + dy[state];
        if (x1 >= 0 && x1 < mx && y1 >= 0 && y1 < my && !vis[x1][y1]) {
            dfs(x1, y1, mx, my, state, matrix, vis, ans);
        } else {
            int state2 = (state + 1) % 4;
            dfs(x + dx[state2], y + dy[state2], mx, my, state2, matrix, vis,
                ans);
        }
    }
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int mx = matrix.size();
        int my = matrix[0].size();
        vector<vector<bool>> vis(mx, vector<bool>(my, false));
        vector<int> ans;
        dfs(0, 0, mx, my, 0, matrix, vis, ans);
        return ans;
    }
};